package seteam12;

import java.util.LinkedHashSet;
import java.util.PriorityQueue;

/**
 * RandomizedSolver class. Tries to solve a Sudoku field using not too stupid
 * random guesses (initial random guess, randomized local search according to
 * fitness function, optional tabu list, restart conditions to avoid getting
 * stuck in local optimums).
 * 
 * @author Dhyan
 * 
 */
public class RandomizedSolver implements Solver {

    public static final boolean SHOW_BASIC_INFO = true;
    public static final boolean DEBUG = false;
    public static final long MAX_RUNTIME_MILLIS = 90000;
    private static double overallTime = 0;

    private long startTimeMillis = 0;
    private long maxEndTimeMillis = 0;
    private PriorityQueue<PrioCell> candidates = null;
    private SudokuBoard board;
    private int[][] initialMatrix = null;
    private long loops = 0;
    private long overallLoops = 0;
    private long attempts = 0;
    private Solution bestSolution = null;
    private Solution currSolution = null;
    private LinkedHashSet<Solution> tabuList = new LinkedHashSet<Solution>();

    @Override
    public boolean solve(final SudokuBoard board) {
	startTimeMillis = System.currentTimeMillis();
	maxEndTimeMillis = startTimeMillis + MAX_RUNTIME_MILLIS;
	this.board = board;
	this.currSolution = new Solution(board.getValues());
	this.bestSolution = currSolution.copy();
	if (SHOW_BASIC_INFO) {
	    System.out.println("RandomizedSolver");
	    System.out.println("This may take 3-90 seconds or even minutes.");
	    System.out.println("The solver will thus stop after 90 secs ;-)");
	    System.out.println("\nInitial board:");
	    board.printBoard();
	}
	setup();
	return findSolution();
    }

    /**
     * Prepares for a new attempt to find a solution
     */
    private void setup() {
	if (bestSolution.getOverallErrors() > currSolution.getOverallErrors()) {
	    bestSolution = currSolution.copy();
	}
	candidates = new PriorityQueue<PrioCell>();
	initialMatrix = board.getValues();
	currSolution.setMatrix(assignRandomNumbers(board.getValues()));
	currSolution.updateErrors();
	loops = 0;
	attempts++;
    }

    /**
     * Tries to solve the given Sudoku matrix. Will modify SudokuBoard in case
     * of success.
     * 
     * @return true if a solution was found, false otherwise
     */
    private boolean findSolution() {
	PrioCell cell1 = null;
	PrioCell cell2 = null;
	int oldErrors = 0;
	while (currSolution.getOverallErrors() > 0) {
	    // Find violating cell
	    cell1 = candidates.poll();
	    cell2 = candidates.poll();
	    oldErrors = currSolution.getOverallErrors();
	    currSolution.swapCells(cell1, cell2);
	    currSolution.updateErrors();
	    // Swap introduced more errors -> undo swap
	    if (currSolution.getOverallErrors() > oldErrors) {
		currSolution.swapCells(cell1, cell2);
		currSolution.updateErrors();
	    }
	    cell1.increasePriority(1);
	    cell2.increasePriority(1);

	    // Add bonus if a cell is not in conflict
	    if (!Solution.isDoubleDigit(cell1, currSolution.getMatrix())) {
		cell1.increasePriority(getRandomInt(8, 16));
	    }
	    if (!Solution.isDoubleDigit(cell2, currSolution.getMatrix())) {
		cell2.increasePriority(getRandomInt(8, 16));
	    }

	    candidates.add(cell1);
	    candidates.add(cell2);
	    loops++;
	    overallLoops++;
	    
	    /*
	     * Long-term rules to promote diversity in the search process (i.e.
	     * regarding resets when the search becomes stuck in a plateau or a
	     * sub-optimal dead-end).
	     */
	    if (loops > 500) {
		if (System.currentTimeMillis() >= maxEndTimeMillis) {
		    break;
		}
		if (DEBUG) {
		    System.out.print("Errors: ");
		    System.out.print(currSolution.getOverallErrors());
		    System.out.print(" Loops: ");
		    System.out.print(loops);
		    System.out.print(" Tabus: ");
		    System.out.println(tabuList.size());
		}
		// if (tabuList.contains(currSolution)) {
		// setup();
		// continue;
		// }
		if (currSolution.getOverallErrors() > 32) {
		    setup();
		    continue;
		}
		if (loops > 1500) {
		    if (currSolution.getOverallErrors() > 16) {
			setup();
			continue;
		    }
		    if (loops > 3000) {
			if (currSolution.getOverallErrors() > 14) {
			    setup();
			    continue;
			}
			if (loops > 8000) {
			    if (currSolution.getOverallErrors() > 12) {
				// addTabu(currSolution.copy());
				setup();
				continue;
			    }
			    if (loops > 12000) {
				if (currSolution.getOverallErrors() > 10) {
				    // addTabu(currSolution.copy());
				    setup();
				    continue;
				}
				if (loops > 16000) {
				    if (currSolution.getOverallErrors() > 6) {
					// addTabu(currSolution.copy());
					setup();
					continue;
				    }
				    if (loops > 20000) {
					if (currSolution.getOverallErrors() > 4) {
					    // addTabu(currSolution.copy());
					    setup();
					    continue;
					}
					if (loops > 30000
						&& currSolution
							.getOverallErrors() > 2) {
					    // addTabu(currSolution.copy());
					    setup();
					    continue;
					}
				    }
				}
			    }
			}
		    }
		}
	    }
	}
	if (bestSolution.getOverallErrors() > currSolution.getOverallErrors()) {
	    bestSolution = currSolution;
	}

	if (SHOW_BASIC_INFO) {
	    System.out.println("Best solution found:");
	    bestSolution.print();
	    System.out.println("Errors: " + bestSolution.getOverallErrors());
	    System.out.println("Loops (this attempt): " + loops);
	    System.out.println("Loops (all attempts): " + overallLoops);
	    System.out.println("Attempts: " + attempts);
	}
	final double time = (System.currentTimeMillis() - startTimeMillis) / 1000.0;
	System.out.println("Consumed time: " + time + " sec");
	overallTime += time;
	if (bestSolution.getOverallErrors() == 0) {
	    board.setValues(bestSolution.getMatrix());
	    return true;
	}
	return false;
    }

    /**
     * @param digit
     *            1-9
     * @return Occurrences of the given digit in the matrix
     */
    private int digitCount(final int digit, final int[][] matrix) {
	int num = 0;
	for (int row = 0; row < matrix.length; row++) {
	    for (int col = 0; col < matrix[0].length; col++) {
		if (matrix[row][col] == digit) {
		    num++;
		}
	    }
	}
	return num;
    }

    /**
     * Add a solution candidate to the tabuList. Remove the head of the list,
     * when the capacity of the tabuList is reached
     * 
     * @param solution
     */
//    private void addTabu(final Solution solution) {
//	if (tabuList.size() >= 60) {
//	    for (Solution sol : tabuList) {
//		tabuList.remove(sol);
//		break;
//	    }
//	}
//	tabuList.add(solution);
//    }

    /**
     * Assigns digits from 1 to 9 to all blank fields in the matrix so that
     * every digit appears exactly 9 times in the whole matrix.
     * 
     * @param matrix
     * @return The given matrix with blank fields replaced by random numbers
     */
    private int[][] assignRandomNumbers(int[][] matrix) {
	for (int row = 0; row < matrix.length; row++) {
	    for (int col = 0; col < matrix[0].length; col++) {
		if (initialMatrix[row][col] == 0) {
		    int value = getRandomInt(1, 9);
		    while (digitCount(value, matrix) > 8) {
			value = (getRandomInt(0, 7) + value) % 9 + 1;
		    }
		    matrix[row][col] = value;
		    candidates.add(new PrioCell(row, col));
		}
	    }
	}
	return matrix;
    }

    /**
     * @param upper
     * @param lower
     * @return Random number between lower (including) and upper (including)
     */
    public static int getRandomInt(final int lower, final int upper) {
	return (int) (lower + (upper - lower + 1) * Math.random());
    }

    public static void main(final String[] args) {
	final RandomizedSolver solver = new RandomizedSolver();
	final SudokuBoard board = new SudokuBoard();
	for (int i = 0; i < 1; i++) {
	    board.setValues(getBoard(1));
	    solver.solve(board);
	}
	System.out.println("Overall consumed time: " + overallTime + " sec");
    }

    /**
     * @param boardNumber
     *            0-4
     * @return
     */
    public static int[][] getBoard(final int boardNumber) {
	int[][][] boards = new int[5][][];
	// Solvable
	boards[0] = new int[][] { { 1, 0, 9, 3, 0, 0, 8, 0, 0 },
		{ 0, 4, 0, 6, 5, 0, 0, 3, 0 }, { 0, 0, 0, 0, 0, 0, 1, 0, 2 },
		{ 0, 9, 5, 1, 0, 0, 0, 8, 0 }, { 0, 2, 0, 0, 8, 9, 6, 0, 4 },
		{ 0, 0, 0, 4, 0, 7, 0, 0, 9 }, { 0, 5, 0, 7, 4, 0, 3, 0, 8 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 6, 0, 2, 0, 0, 0, 0, 7, 0 } };

	// Solvable ?
	boards[1] = new int[][] { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 3, 0, 8, 5 }, { 0, 0, 1, 0, 2, 0, 0, 0, 0 },
		{ 0, 0, 0, 5, 0, 7, 0, 0, 0 }, { 0, 0, 4, 0, 0, 0, 1, 0, 0 },
		{ 0, 9, 0, 0, 0, 0, 0, 0, 0 }, { 5, 0, 0, 0, 0, 0, 0, 7, 3 },
		{ 0, 0, 2, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 0, 4, 0, 0, 0, 9 } };

	// Solvable
	boards[2] = new int[][] { { 1, 2, 0, 4, 0, 0, 3, 0, 0 },
		{ 3, 0, 0, 0, 1, 0, 0, 5, 0 }, { 0, 0, 6, 0, 0, 0, 1, 0, 0 },
		{ 7, 0, 0, 0, 9, 0, 0, 0, 0 }, { 0, 4, 0, 6, 0, 3, 0, 0, 0 },
		{ 0, 0, 3, 0, 0, 2, 0, 0, 0 }, { 5, 0, 0, 0, 8, 0, 7, 0, 0 },
		{ 0, 0, 7, 0, 0, 0, 0, 0, 5 }, { 0, 0, 0, 0, 0, 0, 0, 9, 8 } };

	// Solvable
	boards[3] = new int[][] { { 0, 0, 0, 0, 0, 9, 2, 0, 4 },
		{ 1, 8, 0, 4, 0, 0, 0, 0, 0 }, { 0, 0, 0, 7, 0, 0, 0, 0, 0 },
		{ 4, 0, 0, 2, 6, 0, 0, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 2, 0, 4, 1, 0, 7, 0 }, { 5, 0, 1, 0, 9, 0, 8, 0, 7 },
		{ 0, 3, 0, 0, 0, 8, 0, 2, 0 }, { 0, 0, 8, 0, 0, 3, 6, 0, 9 } };

	// Solvable
	boards[4] = new int[][] { { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
		{ 6, 0, 0, 1, 9, 5, 0, 0, 0 }, { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
		{ 8, 0, 0, 0, 6, 0, 0, 0, 3 }, { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
		{ 7, 0, 0, 0, 2, 0, 0, 0, 6 }, { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
		{ 0, 0, 0, 4, 1, 9, 0, 0, 5 }, { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };
	return boards[boardNumber];
    }
}